package class01;

import utils.ArrayUtil;

/**
 * @ClassName Code04_SelectionSort
 * @Description: 选择排序
 * @Author: WangWenpeng
 * @date: 8:45 2021/5/9
 * @Version 1.0
 */
public class Code04_Sort {

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        ArrayUtil.printArray(arr);
        //selectSort(arr);
        //bubbleSort(arr);
        insertSort(arr);
        ArrayUtil.printArray(arr);
    }

    /**
     * @Description 插入排序
     * @Author WangWenpeng
     * @Date 9:25 2021/5/9
     * @Param [arr]
     */
    private static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //0   -    0    结尾位置在变
        //0   -    1
        //0   -    2
        //0   -    n-1
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            int newNunIndex = end;
            //最后一位和他前一位进行比较   后面的小就交换
            while (newNunIndex - 1 >= 0 && arr[newNunIndex - 1] > arr[newNunIndex]) {
                ArrayUtil.swap(arr, newNunIndex - 1, newNunIndex);
                newNunIndex--;
            }
        }
    }

    /**
     * @Description 优化
     * @Author WangWenpeng
     * @Date 14:04 2021/5/23
     * @Param [arr]
     */
    public static void insertSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            // pre 前一个位置
            for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                ArrayUtil.swap(arr, pre, pre + 1);
            }
        }
    }

    /**
     * @Description 冒泡排序   每次把最大的放到最后
     * @Author WangWenpeng
     * @Date 9:10 2021/5/9
     * @Param [arr]
     */
    private static void bubbleSort(int[] arr) {
        //0  -  n-1    相邻比较 大的往后
        //0  -  n-2
        //0  -  n-3
        if (arr == null || arr.length < 2) {
            return;
        }

        int N = arr.length;
        //每次比较 0到end-1之间  控制比较的范围
        for (int end = N - 1; end >= 0; end--) {
            //  0/1      1/2 2/3  end-1/end    大小比较 左边大就交换  大的往后
            for (int second = 1; second <= end; second++) {
                if (arr[second - 1] > arr[second]) {
                    ArrayUtil.swap(arr, second - 1, second);
                }
            }
        }
    }

    /**
     * @Description 选择排序
     * @Author WangWenpeng
     * @Date 9:02 2021/5/9
     * @Param [arr]
     */
    private static void selectSort(int[] arr) {
        //不需要排序的边界条件
        if (arr == null || arr.length < 2) {
            return;
        }

        //0  ~ n-1  选一个最小值
        //1  ~ n-1
        //2  ~ n-1
        int N = arr.length;
        //在 i - N-1的范围上开始
        for (int i = 0; i < N; i++) {
            int minValueIndex = i;
            //抓最小值的位置  i往后所有走一遍
            for (int j = i + 1; j < N; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            //交换这个区间的i位和最小位 index     交换传参index 不是传值
            ArrayUtil.swap(arr, i, minValueIndex);
        }
    }
}
